home *** CD-ROM | disk | FTP | other *** search
/ QRZ! Ham Radio 8 / QRZ Ham Radio Callsign Database - Volume 8.iso / pc / files / dsp / srffttar.z / srffttar / SRFFT / readme < prev    next >
Text File  |  1991-08-26  |  3KB  |  60 lines
  1. This is my implementation of integer real fft computation. It was
  2. designed for high speed analysis of audio input in real time on a
  3. PC/AT.
  4.  
  5. The data used was 8bit but the routine does 16bit signed arithmetic.
  6. The algorithm of choice was one which minimizes mults while keeping the
  7. number of needed registers to a minimum (the Intel chip does not have
  8. enough). Data if gradualy scaled in flight to avoid overflow.
  9.  
  10. A standard (2,4) split-radix was used as described in [Sorensen et al.,
  11. IEEE ASSP-35 no 6., June 87, pp. 849-863]. Other algoriths (WFT etc.)
  12. where found to use too complex arithmetic for efficient implementation
  13. on a machine with a decent mult instruction.
  14.  
  15. WHAT IT DOES NOT DO:
  16. - NO inverse fft.
  17. - NO complex input.
  18. - NO windowing.
  19. - output is power spectrum WITHOUT the square root taken.
  20. - the data array x[] is not descramled so you cannot use it directly.
  21.   see how the power spectrum is derived if you want to generate
  22.   phase or whatever. fft7() and fft8() function do this post-
  23.   processing.
  24.  
  25. The method of implementaion was to have a program (fftg.c) that
  26. generates the fft routine which is then compiled/assembled and used.
  27. The generated program is assembly, but for portability this release
  28. generates a C program too. I have routines for Intel assembly and ns32k
  29. assembly, other machines can have the basic routines re-written without
  30. much effort (but for best performance one would optimize these routines
  31. extensively).
  32.  
  33. The tar file contains a sample program (fft2.c) that uses the fft routine. It
  34. draws some basic pictute on a screen using move() and draw() function which
  35. you will have to supply (it uses the microsoft c graphics library).
  36.  
  37. Originaly the program started as a BASIC program from some British mag
  38. a few years ago which started my interest as it took a few minutes to
  39. do one fft. The current version does a 256 point fft on a 25MHz ns32532
  40. in 2.9ms, on a 10MHz 80286 it took 7ms (I think, it has a rather fast
  41. int mult).
  42.  
  43. To get the generator programs 'make progs'.
  44.  
  45. To get the fft programs 'make fft'. The 'c' version uses fftsubs.h. The
  46. 'f' version uses C function calls which is a bit slower but uses far
  47. less memory, it uses fftsubs.c. Note that the makefile generates a 256
  48. point routine with entry point fft(), you may want to change it for your
  49. needs or just edit the output.
  50.  
  51. fftouts.c generates ns32k assembly, fftouta.c generates Intel assembly.
  52. These should give a good idea of how to port the assembly level
  53. routines to another machine.
  54.  
  55. To get the test programs 'make tests' (but first fix fft2.c for the
  56. graphics).
  57.  
  58. Please let me know of problems/difficulties you encounter with these
  59. programs.
  60.